高级排序算法 快速排序

快速排序法介绍

基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中二部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

快速排序的时间复杂度为 $O(nlogn)$ ,它的空间复杂度是 $O(logn)$ 最坏情况是 $O(n^2)$

快排：实现原理

每次都取第一位作为基准元素，然后对剩下的进行分组，比第一位小的放在左边，比第一位大的放在右边，如此循环，最后再拼在一起（选取第一位作为基准元素虽然简单，如果逆序的情况就会变成 $O(n^2)$ 所以一般随机选择一个元素作为基准元素）

选定了基准元素以后，要做的就是把其他元素当中小于基准元素的都移动到基准元素一边，大于基准元素的都移动到基准元素另一边。

其实快速排序有一个比较简单的做法，就是递归。对于每一趟排序都是一样的思想，只不过需要进行排序的数组的范围越来越小了，使用递归实现这种排序最适合不过了。

所以快速排序的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分（也可以分成三部，具体看荷兰国旗问题，分成三部分会更快），其中一部分的所有数据比另一部分的所有数据要小，再按这种方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，使整个数据变成有序序列。

荷兰国旗问题（帮助理解快排）

这个荷兰国旗问题就是快排思想的一种应用，把元素分别丢到左右两边

问题一（分成两部分）

给定一个数组 arr，和一个数 num，请把小于等于 num 的数放在数组的左边，大于 num 的数组放在数组右边。要求额外空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

解题思路：

如图，使用两个指针，指针 min 指向比 num 小的数，另一个指针 i 逐步移动，当 i 指向的数比 num 小，则这个数与 min 指针前面那个数交换，然后 min 指针前进一位

public class Main {
    public static void main(String[] args) {
        // int[] arr = new int[]{3, 9, 6, 7, 4, 3, 5, 8, 2};
        int[] arr = generateArray(50, 10);
        sortColors(arr, 5);
        System.out.println(Arrays.toString(arr));
    }

    public static void sortColors(int[] arr, int num) {
        int i = 0;
        // min 要从 -1 开始计数
        int min = -1;
        while (i < arr.length) {
            if (arr[i] <= num) {
                min++;
                // 健壮性判断
                if (min >= arr.length) return;
                // 只有不一样才需要交换
                if (min != i) {
                    // 交换元素
                    int tmp = arr[min];
                    arr[min] = arr[i];
                    arr[i] = tmp;
                }
            }
            i++;
        }
    }

    /**
     * 测试用：生成随机数组
     */
    public static int[] generateArray(int len, int max) {
        int[] arr = new int[len];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * max);
        }
        return arr;
    }
}

问题二（分成三部分）

这个就是正统的荷兰国旗问题了

给定一个数组 arr，和一个数 num，请把小于 num 的数放在数组的左边，等于 num 的数放在中间，大于 num 的数放在数组的右边（与上面的问题区别就是这里分成了三种情况）。要求额外空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

这个问题之所以叫荷兰国旗，是因为我们可以将上面三种情况想象成条状物，有序排列后正好组成荷兰国旗。

这题的题解看 左神这个视频 1:52:00 秒开始的过程

这三种情况：

1. 当 arr[i] < num 时，min 指针下一个元素和 i 指针的元素交换（这里是因为下面 arr[i] == num 时，需要把与 num 相等的数换到中间时 min 才会动，所以这一步主要是为了让相等的部分向中间靠），min++，i++

2. 当 arr[i] == num 时，i++
3. 当 arr[i] > num 时，i 指针的元素和 max 指针前一个元素交换，max--，i 不动（因为刚交换的这个元素是新过来的，num 还没和它比较过，如下图）

public class Main {
    public static void main(String[] args) {
        // int[] arr = new int[]{3, 9, 6, 7, 4, 3, 5, 8, 2};
        int[] arr = generateArray(20, 10);
        int[] arrCopy = Arrays.copyOf(arr, arr.length);

        sortColors(arrCopy, 5);
        System.out.println(Arrays.toString(arr));
        System.out.println(Arrays.toString(arrCopy));
    }

    public static void sortColors(int[] arr, int num) {
        int i = 0;
        // min 要从 -1 开始计数
        int min = -1;
        int max = arr.length;
        while (i < arr.length && i != max) {
            if (arr[i] < num) {
                min++;
                // 只有不一样才需要交换
                if (min != i) {
                    // 交换元素
                    int tmp = arr[min];
                    arr[min] = arr[i];
                    arr[i] = tmp;
                }
                i++;
            }
            // 大于时 i 不动
            else if (arr[i] > num) {
                max--;
                if (max != i) {
                    // 交换元素
                    int tmp = arr[max];
                    arr[max] = arr[i];
                    arr[i] = tmp;
                }
            } else {
                i++;
            }

        }
    }

    /**
     * 生成随机数组
     */
    public static int[] generateArray(int len, int max) {
        int[] arr = new int[len];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * max);
        }
        return arr;
    }
}

挖坑法实现快排 ⛔

快排：挖坑法了解就好（这种方法比较难理解，不像荷兰国旗问题那样好懂，而且效率还低），主要看下面荷兰国旗实现的快排

定义两个指针 left 指向起始位置，right 指向最后一个元素的位置，然后指定一个基数 key（a[right]）作为坑（坑的意思就是这块地方等着数据传进来）

left 寻找比 key 大的数字，找到后将 left 的数据赋给 right，left 成为一个坑（就是不动，等待 right 找到再动）

然后 right 寻找比 key 小的数字，找到将 right 的数据赋给 left，right 成为一个新坑，循环这个过程，直到 begin 指针与 end 指针相遇，然后将 key 最后那个坑交换

最终：key 的左边都是比 key 小的数，key 的右边都是比 key 大的数

过程如这个动图所示：

代码如下所示：

public class QuickSort {
    private int[] array;
    public QuickSort(int[] array) {
        this.array = array;
    }

    public void sort() {
        quickSort(array, 0, array.length - 1);
    }

    public void print() {
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }
   
    /**
     * 递归排序
     * @param src
     * @param begin
     * @param end
     */
    private void quickSort(int[] src, int begin, int end) {
        if (begin < end) { // 别忘了这个健壮性判断

            int key = src[begin]; // 选第一位为坑
            int i = begin;
            int j = end;

            // 开始一轮遍历
            while (i < j) {
                // 从右到左找到第一个比 key 大的值
                while (i < j && src[j] > key) {
                    j--;
                }
        // 找到这个值后先健壮性判断再交换
                if (i < j) {
        // 把 j 的数据传给 i 处，然后 j 处成为坑
                    src[i] = src[j];  // 第一次这里 src[i] 的值已经存到 key 字段里面去了，所以无需担心丢失
        // 这里 j 坑不动，i 动一位（因为原 i 处已经得到值了，所以无需再修改它）
                    i++; 
                }

                // 从左到右找到第一个比 key 小的值
                while (i < j && src[i] < key) {
                    i++;
                }
                // 同上
                if (i < j) {
                    src[j] = src[i]; 
                    j--;
                }
            }

            src[i] = key; // 确保 i 与 j 相遇时把值填回坑里
            quickSort(src, begin, i - 1);
            quickSort(src, i + 1, end);
        }
    }
}

一次调用的执行流程如下，剩下的就是递归，重复这段1

3 4 2 1 5 7 8 6 9 0

key = 3
i = 0
j = 9

这里讨论第一次执行 quickSort 的情况

第一趟
    while j = 8

    9* 4 2 1 5 7 8 6 9' 0 // ' 表示当前坑位， * 表示 i，^ 表示 j （在坑位时不表示）
    i = 1

    while i = 1

    9 4' 2 1 5 7 8 6 4^ 0
    j = 7
第二趟
    while j = 7

    9 6* 2 1 5 7 8 6' 4 0
    i = 2

    while i = 3

    9 6 2' 1 5 7 8 2^ 4 0
    j = 6
第三趟
    while j = 6

    9 6 8* 1 5 7 8' 2 4 0
    i = 3

    while i = 3

    9 6 8 1' 5 7 1^ 2 4 0
    j = 5
第四趟
    while j = 5

    9 6 8 7* 5 7' 1 2 4 0
    i = 4

    while i = 5

结束循环
    9 6 8 7* 5 3 1 2 4 0

使用随机坑位来优化

这里使用 Java 的标准接口来编写

public class Quick {
    // 这里有两个 sort 方法，第一个 sort 方法才是给用户使用的
    public static <T extends Comparable<T>> void sort(T[] a) {
        int low = 0;
        int high = a.length - 1;
        sort(a, low, high);
    }

    private static <T extends Comparable<T>> void sort(T[] a, int low, int high) {
        // 先做安全性校验
        if (low >= high) {
            return;
        }

        // 需要对数组中 low索引到 high索引处的元素进行分组（左子组和右子组）
        int partition = partition(a, low, high); // 返回分界值所在的索引，分界值位置变化后的索引

        // 让左子组有序
        sort(a, low, partition - 1);
        // 让右子组有序
        sort(a, partition + 1, high);
    }

    private static int partition(Comparable[] a, int low, int high) {
        // 定义两个指针，分别指向 left 和 right
        int left = low;
        int right = high + 1;
        Comparable key = a[left]; // 取第一个做分界值

        while (true) {
            // left 找大，从左往右扫描，移动 left 指针，找到一个比分界值大的元素，停止
            while (less(a[++left], key)) {
                if (left == high) {
                    break;
                }
            }

            // right 找小，从右往左扫描，移动 right 指针，找到一个比分界值小的元素，停止
            while (less(key, a[--right])) {
                if (right == low) {
                    break;
                }
            }

            // 判断 left 是否大于等于 right，如果是则表示元素扫描完成，结束循环，如果不是则直接交换元素
            if (left >= right) {
                break;
            } else {
                exchange(a, left, right);
            }
        }

        // 最终交换一下分界值与 left, right 的交点处索引（这里一定要交换 right）
        exchange(a, low, right);
        return right;
    }

    private static <T extends Comparable<T>> boolean less(T v, T w) {
        return v.compareTo(w) < 0;
    }

    private static <T extends Comparable<T>> void exchange(T[] a, int i, int j) {
        T temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

注意！！上面的这个直接取第一个元素作为基准数有个致命的缺点，就是如果是有序的情况下很容易 StackOverflow，不同于归并排序，归并排序基本上就是不断的二分下去，而这个快速排序如果选择第一个或者最后一个元素作为基准数，那倒序时则会开辟同待排序元素个数相同的方法数量。例如倒序 10000个元素，则会开辟 10000个方法，这样很容易导致 StackOverflow

如下的测试方法，直接就 StackOverflow 了

public class Temp {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        for (int i = 10000000; i > 0; i--) {
            list.add(i);
        }

        Integer[] a = new Integer[list.size()];
        list.toArray(a);
        testQuick(a);
    }

    public static void testQuick(Integer[] a) {
        long start = System.currentTimeMillis();
        Quick.sort(a);
        long end = System.currentTimeMillis();
        System.out.println("快速排序执行时间为：" + (end - start) + "毫秒");
    }
}

一种比较常见的优化方法是随机化算法，即随机选取一个元素作为基准。这种情况下虽然最坏情况仍然是 $O(n2)$ ,但最坏情况不再依赖于输入数据，而是由于随机函数取值不佳。实际上，随机化快速排序得到理论最坏情况的可能性仅为 $\frac {1} {2n}$ 。所以随机化快速排序可以对于绝大多数输入数据达到 $O(nlogn)$ 的期望时间复杂度。

只需更改一小部分

private static int partition(Comparable[] a, int low, int high) {
    // 定义两个指针，分别指向 left 和 right
    int left = low;
    int right = high + 1;
    int x=  new Random().nextInt(right - left) + left; // 取得随机基准下标
    exchange(a, left, x); // 再交换一下位置
    Comparable key = a[left];
    // ...

测试方法

public class Temp {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        for (int i = 10000000; i > 0; i--) {
            list.add(i);
        }

        Integer[] a = new Integer[list.size()];
        list.toArray(a);
        testQuick(a);
    }



    // 快速排序执行时间为：1672毫秒
    public static void testQuick(Integer[] a) {
        long start = System.currentTimeMillis();
        Quick.sort(a);
        long end = System.currentTimeMillis();
        System.out.println("快速排序执行时间为：" + (end - start) + "毫秒");
    }
}

基于荷兰国旗问题的快排 ⭐

回顾一下荷兰国旗问题，看下图

其实荷兰国旗问题就是 一次快排，每次快排都是把大于它的，小于它的，各划分为一块区域，那这样 每次都递归 的去划分，就能得到一个有序的数组了

而且它还避免像挖坑法那样，对与自己相等的元素还进行递归（只需递归左右两边，中间无需递归），所以使用这种分成三部分的方式，比上面挖坑法分成两部分的方式效率高的多

把上面荷兰国旗问题的算法简单改一下：

public class Quick {
    public static void main(String[] args) {
        // int[] arr = new int[]{3, 9, 6, 7, 4, 3, 5, 8, 2};
        int[] arr = generateArray(20, 10);
        int[] arrCopy = Arrays.copyOf(arr, arr.length);

        sort(arrCopy, 0, arrCopy.length - 1);

        System.out.println(Arrays.toString(arr));
        System.out.println(Arrays.toString(arrCopy));
    }

    public static void sort(int[] arr, int start, int end) {
        // Base Case
        if (start < 0 || end > arr.length || start >= end) return;

        int i = start;
        // min 要从 -1 开始计数
        int min = start - 1;
        int max = end + 1;
        // 为啥取随机坑位，具体看上面的挖坑法那个解析
        int num =  arr[new Random().nextInt(end - start) + start]; // 取得随机基准下标

        while (i < arr.length && i != max) {
            if (arr[i] < num) {
                min++;
                // 只有不一样才需要交换
                if (min != i) {
                    // 交换元素
                    int tmp = arr[min];
                    arr[min] = arr[i];
                    arr[i] = tmp;
                }
                i++;
            }
            // 大于时 i 不动
            else if (arr[i] > num) {
                max--;
                if (max != i) {
                    // 交换元素
                    int tmp = arr[max];
                    arr[max] = arr[i];
                    arr[i] = tmp;
                }
            } else {
                i++;
            }
        }

        // 此时已经划分好了，再次递归调用
        sort(arr, start, min);
        sort(arr, max, end);
    }

    /**
     * 测试用：生成随机数组
     */
    public static int[] generateArray(int len, int max) {
        int[] arr = new int[len];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * max);
        }
        return arr;
    }
}

快速排序和归并排序的区别

快速排序是另一种分治的排序算法，它将一个数组分成两（或者三个）个子数组，将两部分独立的排序。快速排序和归并排序是互补的：

• 归并排序将数组分成两个子数组分别排序，并将有序的子数组归并从而将整个数组排序
• 而快速排序的方式则是当两个数组都有序时，整个数组自然就有序了（大的在右，小的在左）

在归并排序中，一个数组采用的是二分的方式，所以递归的调用发生在处理整个数组之前，而在快速排序中，切分数组的位置取决于数组的内容，所以递归调用发生在处理整个数组之后

Reference

参考资料 快速排序算法—左右指针法，挖坑法，前后指针法，递归和非递归 参考资料 快速排序算法详解（原理、实现和时间复杂度）